//
//  BinaryTreeNode.hpp
//  tree
//
//  Created by chenyh on 2021/2/5.
//

#ifndef BinaryTreeNode_hpp
#define BinaryTreeNode_hpp
#include <iostream>
/**
 树和二叉树之 间有两个重要的区别:
  树中结点的最大度数没有限制，而二叉树结点的最大度数为 2，即二叉树是结点度数最大为 2 的树。
  普通树的结点无左右之分，表现为无序的，而二叉树的结点有左、右之分，也就 是说二叉树是一种有序数。
 根据研究，二叉树具有一些比较特殊的性质，归纳如下，在这里我们依然不对这些性 质进行证明。
 
 1》具有 n 个结点的非空二叉树有且仅有 n–1 个分支。
 2〉非空二叉树的第 i 层最多有 2i次方–1 个结点。
 3》深度为 k 的二叉树最多有 2k次方 –1 个结点。
 4〉在任意非空二叉树中，若叶子结点的数目为 n0，度为 2 的结点数目为 n2，则 n0=n2+1 成立。
 5》性质 5 具有 n(n>0)个结点的完全二叉树的深度为 k=i/2。
 6〉性质 6 若对一棵具有 n 个结点的完全二叉树的所有结点按层从上到下，每层从左至 右的顺序依次对结点从 1 开始编号，则编号为 i 的结点具有以下性质。
 1 如果 i=1，则结点 i 为二叉树的根结点，无双亲结点;
 2 如果 i>1，则结点 i 的双亲结点编号为i/2;
 3 如果 2i≤n，则编号为 i 的结点的左孩子编号为 2i;如果 2i>n，则该结点没有左孩子。
 4 如果 2i+1≤n，则编号 i 的结点的右孩子编号为 2i+1;如果 2i+1>n，则编号为 i 的
 结点无右孩子。
 */
//构建一棵二叉树
template <typename DataType> class BinaryTree;
template <typename DataType> class BinaryTreeNode
{
private:
    DataType data;
    BinaryTreeNode *lChild;     //左子树指针
    BinaryTreeNode *rChild;     //右子树指针
public:
    friend class BinaryTree<DataType>;
    BinaryTreeNode()
    {
        data = NULL;
        lChild = NULL;
        rChild = NULL;
    }
    // 构建一个指定数据域的结点
    BinaryTreeNode(DataType newData)
    {
        data = newData;
        lChild = rChild = NULL;
    }
    DataType getData()
    {
        if (data != NULL) {
            return data;
        }
        return NULL;
    }
    BinaryTreeNode<DataType> * getLeftNode()
    {
        return lChild;
    }
    
    BinaryTreeNode<DataType> * getRightNode()
    {
        return rChild;
    }
};

template <typename DataType>
class BinaryTree {
private:
    BinaryTreeNode<DataType> *root;
public:
    BinaryTree()
    {
        root = new BinaryTreeNode<DataType>();
    }
    BinaryTree(DataType rootData)
    {
        root = new BinaryTreeNode<DataType>();
        root->lChild = NULL;
        root->rChild = NULL;
    }
    ~BinaryTree()
    {
        BinaryTreeNode<DataType> *node = root;
        if (node != NULL) {
            destroyBT(node->lChild);
            destroyBT(node->rChild);
            delete node;
        }
        delete root;
    }
    
    /**
     二叉树的遍历有 4 种方式:前序遍历、中序遍历、后序遍历 和层序遍历。
     (1)前序遍历 前序遍历是指如果被访问的二叉树非空，我们就遵循如下的顺序去访问二叉树结点: 1 先访问根结点。
     2 遍历左子树。
     3 访问右子树。 按照这样的思路，很容易就可以利用递归思想来实现先序遍历算法，在这里我们采用
     链式存储结构来表示二叉树。
     
     (2)中序遍历 中序遍历是指按照如下的步骤访问二叉树:
     1 遍历二叉树左子树。
     2 访问根结点。
     3 遍历二叉树右子树。
     
     (3)后序遍历 后序遍历遵循如下的步骤:
     1遍历二叉树左子树。
     2遍历二叉树右子树。
     3访问根结点。
     
     
     4)层序遍历 层序遍历有时又称为广度优先遍历方式，这种遍历方式是讲述从根结点开始按层遍
     历，根结点为第 1 层，它的子结点为第 2 层，依次从上到下，从左到右遍历。如果我们将 图 2-10(a)的二叉树按层遍历，得到的结果就是 ABCDEFGHIJ。按层遍历的实现要比前 面 3 种遍历方式稍微复杂一点，我们需要借助队列的帮助。代码如下:
     二叉树是单向指示的层次结构，即指针是由父结点 指向子结点，我们不能直接由某结点 i 去获取其父结点的指针。怎么办呢?在这里可以借 助层序遍历来实现。我们先将给定的结点指针与二叉树的根结点比较，如果相同则该结点 没有父结点，返回 NULL;如果不相同，我们将该二叉树进行层序遍历，将队列中每一个 出队的结点的左孩子结点和右孩子结点与指定结点相比较，如果指定结点与左孩子结点或 者右孩子结点相等，则该出队结点就是指定结点的父结点;如果层序遍历完成没有结点与 指定结点相等，则说明该结点不在二叉树中，返回 NULL。
     
     4.求指定结点i的子结点
     求子结点是最基本的操作之一，由于我们在定义二叉树的时候，将二叉树类 BinaryTree 定义为结点类BinaryTreeNode的友元类，所以可以利用BinaryTree类直接访问结点对象的 左右孩子结点指针。如果没有定义为友元类，也可以将这个方法定义在结点类中，然后在 BinaryTree 类中调用该方法即可。
     
     5.求结点的左兄弟结点或右兄弟结点
     道二叉树是单向分层结构，兄弟结点之间也没有直接联系，所以要获 取结点的兄弟结点，需要通过兄弟结点之间的唯一联系——父结点。因此，可以借助前面 讲过的求父结点的方法来实现我们的目标。
     
     6.求一棵二叉树的高度
     二叉树的高度也叫做二叉树的深度，等于二叉树的叶子结点的最大深度。我们可以利 用二叉树的遍历操作来实现求二叉树的高度。我们以深度优先的策略来遍历二叉树，在遍 历的过程中记录每一个结点的深度和当前的最大深度，遍历结束后返回最大深度。为了能 够实现深度优先的遍历策略，我们设置了两个额外的栈结构，一个存储访问的结点，一个 存储结点对应的深度，为什么要利用栈结构呢?因为在沿着一条向下的路径遍历二叉树时， 不可避免我们初始选择的路径并不是最长的，所以需要随时地退回上一个结点，栈结构地 后进先出原则正好很适合这种路径回溯的方法。
     
     7.将一棵二叉树插入另一棵二叉树的结点i，作为i的左(右)子树
     将一棵二叉树插入另一棵二叉树的某结点，其实就是对二叉树的插入操作，我们只需 要将该子二叉树的根结点插入到指定的结点即可。
     
     9.销毁一棵二叉树
     销毁一棵二叉树是指将二叉树的所有结点从二叉树中删去，并释放这个结点的存储空
     间，将根结点指针设为 NULL，使之成为空二叉树。由于我们是要最后删除根结点，因此
     可以依赖后续遍历来实现。
     
     10.求结点i的深度
     求结点 i 的深度，我们可以假设二叉树中存在值与指定值相等的结点，而且该结点的 个数不多于 1 个。这样问题的关键在于遍历该二叉树然后找到二叉树中存在该结点的那一 条线。我们可以设置两个栈，实现二叉树的后续遍历，这样在找到结点后，栈的栈顶指针 再加 2 就是该结点的深度。加 2 的原因是栈顶的初始游标设置为–1。
     */
    
    
    /// 前序遍历
    /// @param node 结点
    void preOrder(BinaryTreeNode<DataType> *node);
    
    /// 中序遍历
    /// @param node 结点
    void inOrder(BinaryTreeNode<DataType> *node);
    
    /// 后序遍历
    /// @param node 结点
    void postOrder(BinaryTreeNode<DataType> *node);
    
    /// 层序遍历
    /// @param node 结点
    void layOrder(BinaryTreeNode<DataType> *node);
    
    /// 寻找父结点
    /// @param node 子结点
    BinaryTreeNode<DataType> * parentNode(BinaryTreeNode<DataType> *node);
    
    /// 求指定结点i的左子结点
    /// @param node 指定结点
    BinaryTreeNode<DataType> * getLChild(BinaryTreeNode<DataType> *node);
    /// 求指定结点i的右子结点
    /// @param node 指定结点
    BinaryTreeNode<DataType> * getRChild(BinaryTreeNode<DataType> *node);
    
    /// 求指定结点i的兄弟结点
    /// @param node 指定结点
    BinaryTreeNode<DataType> * getBrotherNode(BinaryTreeNode<DataType> *node);
    
    int getDepth(int numberofNodes);
    /// 将一棵二叉树插入另一棵二叉树的结点i，作为i的左(右)子树
    /// @param bt 要插入的二叉树
    /// @param node 被插入的结点
    void insertSubBT(BinaryTree<DataType> *bt,BinaryTreeNode<DataType> *node);
    
    /// 删除结点i的左（右）子树
    /// @param node 结点
    void deleteNodes(BinaryTreeNode<DataType> * node);
    
    
    /// 删除子数
    /// @param node 结点
    /// @param i 1为选择数，1表示删除左子树，2表示删除右子树，3表示两个子树都删除
    bool deleteSubTree(BinaryTreeNode<DataType> *node,int i);
    
    
    /// 销毁一颗二叉树
    /// @param node 结点
    void destroyBT(BinaryTreeNode<DataType> *node);
    
    int  getDepthOfNode(DataType i);
};

template <typename DataType>
void BinaryTree<DataType>:: preOrder(BinaryTreeNode<DataType> *node) {
    if (node != NULL) {
        std::cout<<node->getData()<<std::endl;
        preOrder(node->getLeftNode());
        preOrder(node->getRightNode());
    }
}

template <typename DataType>
void BinaryTree<DataType>:: inOrder(BinaryTreeNode<DataType> *node) {
    if (node != NULL) {
        inOrder(node->getLeftNode());
        std::cout<<node->getData()<<std::endl;
        inOrder(node->getRightNode());
    }
}

template <typename DataType>
void BinaryTree<DataType>:: postOrder(BinaryTreeNode<DataType> *node) {
    if (node != NULL) {
        postOrder(node->getLeftNode());
        postOrder(node->getRightNode());
        std::cout<<node->getData()<<std::endl;
    }
}

template <typename DataType>
BinaryTreeNode<DataType> * BinaryTree<DataType>:: parentNode(BinaryTreeNode<DataType> *node) {
    if (node == NULL || node == root ) {
        return NULL;
    }
    int max = 50;           //队列大小，在不知道树的大小之前尽量设置大一点
    int front,rear;         //设置队首队尾
    BinaryTreeNode<DataType> *current,*child;  //设置指向当前结点的指针
    int count = 0;                      //队列中的元素个数
    if (node != NULL) {
        DataType (*queue) = new DataType[max]; //为队列申请空间
        front = rear = 0;       //初始化队列指针
        queue[rear] = node;     //将初始根结点入队
        rear++;                 //队尾指针后移
        count++;                //元素个数加1
        while (count != 0) {
            current = queue[front];     //队首元素出队，设置为当前结点
            std::cout<<current->getData()<<std::endl;//输出队首元素的值
            if (current->getLeftNode() != NULL) {
                child = current->getLeftNode();
                if (child == node) {
                    return current;
                }
                queue[rear] = child;
                rear = (rear+1)%max;
                current++;
            }
            if (current->getRightNode() != NULL) {
                //判断出队元素的右子结点是否为空，若不为空，则入队
                child = current->getRightNode();
                if (child == node) {
                    return current;
                }
                queue[rear] = child;
                rear = (rear+1)%max;
                count++;
            }
            front = (front+1)%max; //出队操作后重新设置队首指针
            count--; //队列中元素个数减1
        }
        return NULL;
    }
}

template <typename DataType>
void BinaryTree<DataType>:: layOrder(BinaryTreeNode<DataType> *node) {
    int max = 50;           //队列大小，在不知道树的大小之前尽量设置大一点
    int front,rear;         //设置队首队尾
    BinaryTreeNode<DataType> *current;  //设置指向当前结点的指针
    int count = 0;                      //队列中的元素个数
    if (node != NULL) {
        DataType (*queue) = new DataType[max]; //为队列申请空间
        front = rear = 0;       //初始化队列指针
        queue[rear] = node;     //将初始根结点入队
        rear++;                 //队尾指针后移
        count++;                //元素个数加1
        while (count != 0) {
            current = queue[front];     //队首元素出队，设置为当前结点
            std::cout<<current->getData()<<std::endl;//输出队首元素的值
            if (current->getLeftNode() != NULL) {
                queue[rear] = current->getLeftNode();
                rear = (rear+1)%max;
                current++;
            }
            if (current->getRightNode() != NULL) {
                //判断出队元素的右子结点是否为空，若不为空，则入队
                queue[rear] = current->getRightNode();
                rear = (rear+1)%max;
                count++;
            }
            front = (front+1)%max; //出队操作后重新设置队首指针
            count--; //队列中元素个数减1
        }
        
    }
}
template <typename DataType>
BinaryTreeNode<DataType> * BinaryTree<DataType>:: getBrotherNode(BinaryTreeNode<DataType> *node) {
    if (node == NULL) {
        return NULL;
    }
    BinaryTreeNode<DataType> *parent = parentNode(node);
    if (parent == NULL) {
        return NULL;
    }
    if (parent->lChild == node) {  //如果指定结点是左孩子，则返回父结点的右孩子
        return parent->rChild;
    }
    if (parent->rChild == node) {
        return parent->lChild;
    }
}

template <typename DataType>
BinaryTreeNode<DataType> * BinaryTree<DataType>:: getLChild(BinaryTreeNode<DataType> *node) {
        
    if (node == NULL) {
        return NULL;
    }
    return node->lChild;

}
template <typename DataType>
BinaryTreeNode<DataType> * BinaryTree<DataType>:: getRChild(BinaryTreeNode<DataType> *node) {
    
    if (node == NULL) {
        return NULL;
    }
    return node->rChild;
}

template <typename DataType>
int BinaryTree<DataType>:: getDepth(int numberofNodes) {
    
    BinaryTreeNode<DataType> *nodeStack = new BinaryTreeNode<DataType>(numberofNodes);//设置存储二叉树结点的栈
    int depthStack[numberofNodes]; //声明深度栈
    int currentDepth,maxDepth=0;//currentDepth表示当前的深度，maxDepth表示最大深度
    int top = -1; //栈的游标指针初始值
    BinaryTreeNode<DataType> *node = root;
    if (node != NULL) {
        currentDepth = 1; //初始化当前深度为1，根结点为第一层
        do {
            while (node != NULL) {
                nodeStack[++top] = node;// 将访问到的不为空的结点入栈，直至遇到空结点后停止
                depthStack[top] = currentDepth;//将相应的深度入栈
                node = node->lChild;    //继续访问当前结点的左孩子
                currentDepth++; // 当前深度加1
            }
            currentDepth = depthStack[top--]; //一条路径走到尽头时，出栈栈顶元素尝试新路径
            if (node->lChild == NULL && node->rChild == NULL) {
                if (currentDepth > maxDepth) { //如果该叶子结点的深度大于最大深度
                    maxDepth = currentDepth;
                }
            }
            node = node->rChild; //开始访问出栈结点的右子树
            currentDepth++;
        //访问结点为空且栈空时循环结束，此时最大的深度就是树的高度
        } while (!(node == NULL && top == -1));
    }
    return maxDepth;
}

template <typename DataType>
void BinaryTree<DataType>:: insertSubBT(BinaryTree<DataType> *bt, BinaryTreeNode<DataType> *node) {
    if (node == NULL && bt->root == NULL) { //判断待插入的子树和插入点是否为空
        return;
    }
    if (node->lChild == NULL) { //如果待插入点左子树为空，则插入到左子树
        node->lChild = bt->root;
    }else if (node->rChild == NULL)
        node->rChild = bt-root;
    else
    {
        BinaryTreeNode<DataType> *p = node->lChild;
        node->lChild = bt->root;
        delete p;
    }
}
template <typename DataType>
void BinaryTree<DataType>:: deleteNodes(BinaryTreeNode<DataType> *node) {
    if (node != NULL) {
        deleteNodes(node->lChild);//递归遍历然后删除遍历的结点
        deleteNodes(node->rChild);
        delete node;
    }
}

template <typename DataType>
bool BinaryTree<DataType>:: deleteSubTree(BinaryTreeNode<DataType> *node, int i) {
    if (node == NULL) {
        return false;
    }
    BinaryTreeNode<DataType> *p;    //声明临时变量
    switch (i) {
        case 1:
            p = node->lChild;
            deleteNodes(p);         //调用删除所有结点函数
            node->lChild = NULL;
            return true;
        case 2:
            p = node->rChild;
            deleteNodes(p);         //调用删除所有结点函数
            node->rChild = NULL;
            return true;
        case 3:
            p = node->lChild;
            deleteNodes(p);         //调用删除左所有结点函数
            node->lChild = NULL;
            p = node->rChild;
            deleteNodes(p);         //调用删除右所有结点函数
            node->rChild = NULL;
            return true;
    }
    return false;
}


template <typename DataType>
void BinaryTree<DataType>:: destroyBT(BinaryTreeNode<DataType> *node) {
    if (node != NULL) {
        destroyBT(node->lChild);//后序遍历所有结点，并删除相应结点
        destroyBT(node->rChild);
        delete node;
    }
    root = NULL;                //将根结点置为null.形成空树
}

template <typename DataType>
int BinaryTree<DataType>:: getDepthOfNode(DataType i) {
    int stackSize = 50;
    BinaryTreeNode<DataType> *nodeStack = new BinaryTreeNode<DataType>[stackSize];//设置存储二叉树结点的栈
    int flagStack[stackSize];               //存储每个结点的状态
    int flag = 0;//flag表示每个结点的访问状态，0表示访问一次，1表示访问两次
    int top = -1;//栈的游标指针初始值
    BinaryTreeNode<DataType> *node = root;//设置当前访问的结点指针并初始化为根结点
    /*循环后序遍历树，讲访问的结点入栈
     检查是否访问的结点就是待求结点
     */
    do {
        
        while (node != NULL) {
            nodeStack[++top] = node;
            flagStack[top] = 0; //将相应结点访问状态入栈，第一次访问状态为0
            node = node->lChild; //继续访问当前结点的左孩子
        }
        node = nodeStack[top];//一条路走到尽头时，出栈栈顶元素尝试新路径
        flag = flagStack[top--]; //获取结点的访问状态
        if (flag == 0) {
            nodeStack[++top] = node;//讲第一次访问的结点再次入栈
            flagStack[top] = 1;//改变相应的访问状态
            node = node->rChild;
        }else
        {
            if (node->data == i) { //如果结点第2次访问则判断其是否为我们需要寻找的结点
                return top+2;//如果找到该结点，则其深度为栈中元素个数+1，即栈顶指针+2
            }
            node = NULL; //如果不是该结点，则继续出栈
        }
    } while (!(node == NULL && top == -1));//访问结点为空且栈空时循环结束
    

}


/*：实例应用与分析
 【例 2-3】有如下数据结构:
 
 */
//请实现两棵树是否相等的比较，如相等返回 0，否则返回其他值。
/**
 【分析】两棵树是否相等当且仅当两棵树的根结点相等，并且其左右子树也相等的情 况下才成立。比如两棵树 A 和 B，那么它们相等的唯一条件就是 RootA->c==RootB->c，并
 且它们的左右子树对应相等或者交换后相等。
 */
typedef struct _TreeNode
{
    char c;
    _TreeNode *leftchild;
    _TreeNode *rightchild;
}TreeNode_t;

int compareTree(TreeNode_t *tree1,TreeNode_t *tree2)
{
    bool isTree1Null = (tree1 == NULL); //判断是否为空概念设计
    bool isTree2Null = (tree2 == NULL);
    if (isTree1Null != isTree2Null) {   //一个空树一个不是空树肯定不相等
        return 1;
    }
    if (isTree1Null && isTree2Null) { //两个都为null肯定相等
        return 0;
    }
    if (tree1->c != tree2->c) { //根结点不相等肯定不等
        return 1;
    }
    return (
            (compareTree(tree1->leftchild,tree2->leftchild) & compareTree ( tree1-> rightchild,tree2->rightchild)) |
    (compareTree(tree1->leftchild,tree2->rightchild)&compareTree(tree1-> rightchild,tree2->leftchild)
     )
            );
}
/**
 【例 2-4】 根据一棵二叉树的前序遍历和中序遍历重建这棵树。
 【分析】根据二叉树的遍历的性质可以知道，前序遍历可以确定二叉树的根结点，中 序遍历可以区分二叉树的左右子树。根据这两个特性，我们可以很轻松地重构整棵二叉树。
 */
typedef struct _node {
    char  data;
    _node * left;
    _node * right;
}node_t;
//通过前序遍历和中序遍历的序列重建二叉树
void ReBuild(char * pPreOrder,char * pInOrder,int nTreeLen,node_t ** pRoot)
{
    if (pPreOrder == NULL || pInOrder == NULL) {
        return;
    }
    //获取前序遍历的第一个结点
    node_t *temp = new node_t;
    temp->data = *pPreOrder;
    temp->left = NULL;
    temp->right = NULL;
    //如果结点为空，把当前结点复制到根结点
    if (*pRoot == NULL) {
        *pRoot = temp;
    }
    //如果当前树长为1，那么已经是最后一个结点
    if (nTreeLen == 1) {
        return;
    }
    //寻找子树长度
    char *pOrgInOrder = pInOrder;
    char *pLeftEnd    = pInOrder;
    int nTempLen = 0;
    //找到左子树的结尾
    while (*pPreOrder != *pLeftEnd) {
        if (pPreOrder == NULL || pLeftEnd == NULL) {
            return;
        }
        //记录临时长度，以免溢出
        nTempLen++;
        if (nTempLen > nTreeLen) {
            break;
        }
        pLeftEnd++;
    }
    //寻找左子树长度
    int nLeftLen = (int)(pLeftEnd-pOrgInOrder);
    //寻找右子树长度
    int nRightLen = nTreeLen-nLeftLen-1;
    //重建左子树
    if (nLeftLen > 0) {
        ReBuild(pPreOrder+1, pInOrder, nLeftLen, &((*pRoot)->left));
    }
    if (nRightLen > 0) {
        ReBuild(pPreOrder+nLeftLen+1, pInOrder+nLeftLen+1, nRightLen, &((*pRoot)->right));
    }

}

#endif /* BinaryTreeNode_hpp */
